package chapter_05;

// 单链表
/*
这个链表仅有的操作是：
1. 在链表头插入一个数据项。
2. 在链表头删除一个数据项。
3. 遍历链表显示它的内容。
 */

public class Link {
    public int iData;
    public double dData;
    public Link next;

    public Link(int id, double dd) {
        iData = id;
        dData = dd;
    }

    public void displayLink() {
        System.out.print("{" + iData + ", " + dData + "} ");
    }
}


class LinkList {
    private Link first;
    // first引用的是当前的节点
    /*
    LinkList的构造函数把first赋成null值。实际上这不是必须的，引用类型在创建之初会自动赋成
    null值。然而，构造函数明确地说明了赋初值，从而强调first是怎么开始运作的。
    当first的值为null时，就表明链表中没有数据项。如果有，first字段中应该存有对第一个链节点
    的引用值。isEmpty()方法用这种方法来判断链表是否为空。
     */

    public void LinkList() {
        first = null;
    }

    public boolean isEmpty() {
        return first == null;
    }

    public void insertFirst(int id, double dd) {
        // 插入一个新节点
        Link newLink = new Link(id, dd);
        newLink.next = first;       // first原来指向的是第一个节点
        first = newLink;            // first --> newLink
    }

    public Link find(int key) {
        // 根据指定的值找到匹配的第一个节点
        if (isEmpty())
            return null;
        Link current = first;
        while (current.iData != key) {
            if (current.next == null)
                return null;
            current = current.next;
        }
        return current;
    }

    public Link delete(int key) {
        // 根据指定的值删除找到的第一个节点
        if (isEmpty())
            return null;
        Link current = first;
        Link previous = first;
        while (current.iData != key) {
            /*
            在while语句的每一轮循环中，每当current变量赋值为current.next之前，
            先把previous变量赋值为current。这保证了它总是指向current所指链节点
            的前一个链节点。
             */
            if (current.next == null)
                return null;
            // 向后移动
            previous = current;
            current = current.next;
        }
        /*
        一旦发现当前节点是要被删除的节点，就把前一个节点的next字段赋值为当前节点的下一个节点。
        如果当前节点是第一个节点，这是一个特殊情况，因为这是由LinkList对象的first域指向的节点，
        而不是别的节点的next所指的。在这种情况下，使first字段指向first.next，就可以删除第一个
        节点。
         */
        if (current == first)
            // 在头结点即找到了要查找的值
            first = first.next;
        else
            // 当前节点的前节点指向当前节点的下个节点
            // previous.next是指向当前节点的，current.next是当前节点的下节点
            previous.next = current.next;
        return current;
    }

    public Link deleteFirst() {     // delete first item
        // 从表头开始删除节点
        Link temp = first;
        first = first.next;
        return temp;
    }

    public void displayList() {
        System.out.println("List (first --> last): ");
        Link current = first;
        while (current != null) {
            current.displayLink();
            current = current.next;
        }
        System.out.println();
    }
}


class LinkListApp {

    public static void main(String[] args) {
        LinkList theList = new LinkList();
        theList.insertFirst(22, 2.99);
        theList.insertFirst(44, 4.99);
        theList.insertFirst(66, 6.99);
        theList.insertFirst(88, 8.99);
        theList.displayList();

//        while (!theList.isEmpty()) {
//            Link aLink = theList.deleteFirst();
//            System.out.print("Deleted ");
//            aLink.displayLink();
//            System.out.println();
//        }
//        theList.displayList();

        // 指定查找和指定删除
        Link f = theList.find(44);
        if (f != null)
            System.out.println("Found link with key " + f.iData);
        else
            System.out.println("Can't find link");

        Link d = theList.delete(66);
        if (d != null)
            System.out.println("Deleted link with key " + d.iData);
        else
            System.out.println("Can't delete link");
        theList.displayList();
    }
}